A good switch arbitration algorithm is an important component of any highspeed switch, router, bridge, or other switching device. The objective of maintaining a high throughput while maintaining certain fairness standards makes the switch arbitration problem a nontrivial one. While a number of approaches have been proposed, it is still a fairly open problem with an ongoing quest for satisfactory solutions.
A typical switch includes an ingress, a switching fabric, and an egress. Network traffic arrives at the ingress and is forwarded through the switching fabric to the egress. In high-speed routers, the most common switch architecture is a crossbar. Among the ingresses of a crossbar switch, there may be a number of cells targeting the same egress.
There are two key measures of the performance of a switch scheduler. First is throughput, which is a measure of egress channel utilization. A scheme that leads to egress ports sitting idle at times is clearly not a good scheme. The other measure of performance is fairness. Each incoming flow should get a fair chance to send and not be starved, but when flows are of different priorities they should be forwarded accordingly. The problem then becomes even more complicated.
Coming up with an algorithm that maximizes performance with respect to throughput, fairness, and priority is a very difficult task. The problem grows even more difficult with the increased complexity and number of ports in modern switches. Crossbar size increases quadratically with the number of ports. As complexity increases, computation time decreases. While there may be good algorithms for arbitration, a solution that can be implemented quickly is of greatest importance. In the absence of such a solution, switch arbitration could become a performance-degrading bottleneck.
The switch arbitration problem is the problem of matching incoming cells to egresses. Each cell targets an egress, based upon its destination. (Unicast cells target one egress, while multicast cells may target multiple egresses). In the simplest case, incoming cells are stored in a first-in-first-out (FIFO) queue at the ingress. However, when a cell at the head of the queue targets an egress that is busy, the cell will block all other cells in the queue from being forwarded. For example, a cell that targets a free egress will not be transferred if it is not at the head of the FIFO queue. This is referred to as head-of-line (HOL) blocking. To solve the HOL blocking, each cell at the ingress could be stored in a different buffer. This improves performance but makes the problem significantly more complicated, essentially a complicated bi-partite graph matching problem.
Additional complexity comes from, for example, setting priorities for certain queues or making quality of service (QoS) guarantees. In some cases, different scheduling algorithms may be selected for use with different subsets of queues. The two most popular scheduling algorithms are strict priority and weighted fair queuing (WFQ). With strict priority, cells are forwarded from higher priority queues first. This algorithm is relatively straightforward to implement. However, a strict priority policy may allow higher priority traffic to completely starve lower priority traffic. With WFQ, the scheduler applies a weight to each queue and then uses a round robin algorithm tempered by the weights. Weights are generally assigned relative to the proportion of bandwidth allocated for each queue. WFQ algorithms are more difficult to implement than strict priority, but are used anyway because of the desire to avoid starving lower priority traffic. However, many of these algorithms, such as longest queue first (LQF), become excessively difficult and costly to implement in high-speed switches. Though not as popular, it should be noted that round robin algorithms work just as well as weighted algorithms when traffic has a uniform pattern. However, if traffic is non-uniform, some Ingresses might be loaded more than others, making round robin unfair in some cases. Strict priority and WFQ are often combined in a two-level scheme so that highest priority traffic is sent first in accordance with strict priority, and lower priority traffic is sent according to the WFQ algorithm. However, this introduces dependencies that undermine the quality of the solution. Another approach is to centralize arbitration to achieve maximum control, but as a switching fabric increases in size, the complexity of a centralized arbitration increases dramatically. Accordingly, the search continues for improved arbitration algorithms.
Due to the difficulty in implementing an arbitration algorithm with a balance of fairness and throughput, as well as a priority bias, a new priority-biased arbitration that maximizes throughput while maintaining fairness is desirable. The algorithm should be practical for implementation in a high-speed switch and sufficiently simple that the switch does not become a network bottleneck. Preferably, the implementation is scalable to larger, more complex switches.